/**
 *    Copyright (C) 2009 Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_DYNVECTOR_MODEL_INSERT_HPP
#define	_CUBEFS_CORE_DYNVECTOR_MODEL_INSERT_HPP

#include <cubefs/core/container/container.hpp>

#include <cubefs/core/btree/btree.hpp>

#include <cubefs/core/dynvector/names.hpp>
#include <cubefs/core/dynvector/pages/data_page.hpp>

#include <cubefs/core/tools/types/typelist.hpp>
#include <cubefs/core/tools/assert.hpp>

#include <cubefs/api/models/model.hpp>


#define CUBEFS_SOURCE "cubefs/core/dynvector/model/insert.hpp:" CUBEFS_AT

namespace cubefs    {
namespace ctr       {

using namespace cubefs::btree;

CUBEFS_MODEL_PART_BEGIN(cubefs::dynvector::InsertName)
private:

public:

    typedef typename Base::Types                                                Types;
    typedef typename Base::PageMgr                                              PageMgr;

    typedef typename PageMgr::Page                                              Page;
    typedef typename Page::ID                                                   ID;

    typedef typename Types::NodeBase                                            NodeBase;
    typedef typename Types::Counters                                            Counters;
    typedef typename Base::Iterator                                             Iterator;

    typedef typename Types::Pages::NodeDispatcher                               NodeDispatcher;
    typedef typename Types::Pages::RootDispatcher                               RootDispatcher;
    typedef typename Types::Pages::LeafDispatcher                               LeafDispatcher;
    typedef typename Types::Pages::NonLeafDispatcher                            NonLeafDispatcher;
    typedef typename Types::Pages::NonRootDispatcher                            NonRootDispatcher;

    typedef typename Types::Pages::Node2RootMap                                 Node2RootMap;
    typedef typename Types::Pages::Root2NodeMap                                 Root2NodeMap;

    typedef typename Base::Metadata                                             Metadata;

    typedef typename Base::Key                                                  Key;
    typedef typename Base::Value                                                Value;

    typedef typename Types::DataPageType                                        DataPageType;
    typedef typename Types::BufferType                                          Buffer;
    typedef typename Types::BufferContentDescriptorType                         BufferContentDescriptor;
    typedef typename Types::CountDataType                                       CountData;


    static const Int Indexes                                                    = Types::Indexes;


//PUBLIC API:

    void InsertDataBlock(Iterator &iter, Buffer &block, BufferContentDescriptor &descriptor)
    {
        // offset, start, length

        NodeBase *page = iter.page();
//        BigInt prefix = 0;

        NodeBase*  index_out    = iter.page();
        BigInt     idx_out      = index_out != NULL ? index_out->parent_idx() : -1;
        BigInt     offset_out   = iter.idx();

        BigInt page_size = DataPageType::get_max_size();

        if (iter.IsEmpty())
        {
            CUBEFS_TRACE(me_, "InsertDataBlock: empty iterator", block.GetByteSize(), me_.root());

            if (me_.root().is_null())
            {
                page = me_.CreateNode(0, true, true);
                me_.set_root(page->id());
            }
            else {
                page = me_.GetRoot();
            }

            index_out = page;

            import_pages(page, 0, 0, block, descriptor, &index_out, idx_out, offset_out);

            iter.reset_state();
            
            iter.SetStart(true);
            iter.idx() = 0;
            iter.data() = me_.GetDataPage(page, 0);
        }
        else
        {
            BigInt bit_idx = iter.idx();
            BigInt usage = me_.GetKey(page, 0, iter.data()->parent_idx());
            CountData &base_prefix = descriptor.base_prefix();

            if (usage + descriptor.length() <= page_size)
            {
                base_prefix = iter.get_base_prefix();

                import_small_block(iter.page(), iter.data()->parent_idx(), bit_idx, block, descriptor);

                index_out = iter.page();
                idx_out = iter.data()->parent_idx();
                offset_out = bit_idx;
            }
            else if (!iter.IsEof())
            {
                if (bit_idx > 0)
                {
                    BigInt idx = iter.data()->parent_idx();
                    if (idx < me_.GetChildrenCount(page) - 1)
                    {
                        if (page_size - me_.GetKey(page, 0, idx + 1) >= usage - bit_idx)
                        {
                            move_data_in_page(iter, bit_idx, base_prefix);
                        }
                        else if (me_.GetCapacity(page) > 0)
                        {
                            me_.InsertSpace(page, idx + 1, 1);
                            me_.create_datapage(page, idx + 1);
                            move_data_in_page(iter, bit_idx, base_prefix);

                            idx_out = idx;
                            index_out = page;
                        }
                        else
                        {
                            me_.SplitBTreeNode(page, idx + 1, 0);
                            move_data_in_page_create(iter, bit_idx, base_prefix);
                        }
                    }
                    else if (idx == me_.GetMaxCapacity(page) - 1)
                    {
                        page = me_.SplitBTreeNode(page, idx, 0);

                        iter.idx() = 0;
                        iter.page() = page;

                        move_data_in_page(iter, bit_idx, base_prefix);
                    }
                    else
                    {
                        move_data_in_page(iter, bit_idx, base_prefix);
                    }
                }
                else
                {
                    base_prefix = iter.get_base_prefix();
                }

                import_pages(iter.page(), iter.data()->parent_idx(), iter.idx(), block, descriptor, &index_out, idx_out, offset_out);
            }
            else
            {
                base_prefix = iter.get_base_prefix();
                import_pages(iter.page(), iter.data()->parent_idx(), iter.idx(), block, descriptor, &index_out, idx_out, offset_out);
            }
        }

        iter.SetEof(false);
        iter.page() = index_out;
        iter.idx()  = offset_out;
        iter.data() = me_.GetDataPage(index_out, idx_out);
    }


//PROTECTED API:
    DataPageType* create_datapage(NodeBase* node, Int idx)
    {
        CUBEFS_TRACE(me_, "create_datapage", node->id(), idx);

        DataPageType *data      = new (me_.mgr()) DataPageType;

        data->parent_idx()      = idx;
        data->parent_id()       = node->id();

        node->model_hash()      = me_.hash();
        node->page_type_hash()  = DataPageType::hash();

        me_.SetLeafData(node, idx, data->id());

        return data;
    }




private:

    void import_pages(
            NodeBase *node,
            BigInt idx,
            BigInt pos,
            Buffer &block,
            BufferContentDescriptor &descriptor,
            NodeBase **page0, 
            BigInt &idx0,
            BigInt &offset0)
    {
        CUBEFS_TRACE(me_, "import_pages", node->id(), idx, pos, block.GetByteSize(), descriptor.start(), descriptor.length(), (*page0)->id(), idx0, offset0);

        BigInt length  = descriptor.length();

        BigInt page_size = DataPageType::get_max_size();
        BigInt fp_capacity = page_size - me_.GetKey(node, 0, idx);

        BigInt size_prefix;

        if (pos == page_size)
        {
            size_prefix = fp_capacity >= length ? length : fp_capacity;
            pos = 0;
            if (idx < me_.GetChildrenCount(node) - 1)
            {
                if (me_.GetCapacity(node) > 0)
                {
                    me_.InsertSpace(node, idx + 1, 1);
                    me_.create_datapage(node, idx + 1);
                }
                else
                {
                    me_.SplitBTreeNode(node, idx + 1, 0);
                }
                idx++;
            }
            else if (idx < me_.GetMaxCapacity(node) - 1)
            {
                idx++;
            }
            else
            {
                node = me_.SplitBTreeNode(node, idx, 0);
                idx = 0;
            }
        }
        else if (pos == 0)
        {
            size_prefix = 0;
        }
        else
        {
            size_prefix = fp_capacity >= length ? length : fp_capacity;
        }

        //BigInt bit_prefix = 0;//, rank, bitsize;
        //descriptor.prefix() = 0; //??? bit_prefix = 0;

        if (size_prefix > 0)
        {
            CUBEFS_TRACE(me_, "import_pages: size_prefix", size_prefix);

            descriptor.length() = size_prefix;
            import_small_block(node, idx, pos, block, descriptor);

            *page0  = node;
            idx0   = idx;
            offset0 = pos;

            descriptor.start() += size_prefix;
            idx++;
        }

        BigInt total_npages = (length - size_prefix) / page_size;
        BigInt size_suffix = length - size_prefix - total_npages * page_size;

        BigInt index_page_size = me_.GetMaxCapacity(node);
        BigInt fpi_capacity = me_.GetCapacity(node);

        CUBEFS_TRACE(me_, "import_pages: values", total_npages, size_suffix, index_page_size, fpi_capacity);

        BigInt index_prefix;

        if (idx == index_page_size)
        {
            index_prefix = 0;
        }
        else if (idx == me_.GetChildrenCount(node))
        {
            index_prefix = fpi_capacity >= total_npages ? total_npages : fpi_capacity ;
        }
        else if (total_npages > fpi_capacity)
        {
            CUBEFS_TRACE(me_, "import_pages: split node");
            me_.SplitBTreeNode(node, idx, 0);

            fpi_capacity = me_.GetCapacity(node);
            index_prefix = fpi_capacity >= total_npages ? total_npages : fpi_capacity;
        }
        else if (total_npages > 0)
        {
            CUBEFS_TRACE(me_, "import_pages: insert space");
            me_.InsertSpace(node, idx, total_npages);
            index_prefix = total_npages;
        }
        else
        {
            index_prefix = total_npages;
        }

        BigInt total_index_pages = (total_npages - index_prefix) / index_page_size;

        CUBEFS_TRACE(me_, "import_pages: total_index_pages", total_index_pages, total_npages, index_page_size);

        if (index_prefix > 0)
        {
            CUBEFS_TRACE(me_, "import_pages: index_prefix", index_prefix);
            descriptor.length() = index_prefix * page_size;

            import_several_pages(node, idx, block, descriptor, index_prefix);

            if (size_prefix == 0)
            {
                *page0  = node;
                idx0    = idx;
                offset0 = 0;
            }

            descriptor.start() += index_prefix * page_size;
            idx += index_prefix;
        }

        if (size_prefix == 0 && index_prefix == 0 && total_index_pages > 0)
        {
            *page0      = node;
            idx0        = idx;
            offset0     = 0;
        }

        BigInt c;
        for (c = 0; c < total_index_pages; c++)
        {
            node = me_.SplitBTreeNode(node, me_.GetChildrenCount(node), 0);
            import_several_pages(node, 0, block, descriptor, index_page_size);

            descriptor.start() += index_page_size * page_size;
            idx = me_.GetMaxCapacity(node);
        }

        BigInt index_suffix = total_npages - index_prefix - total_index_pages * index_page_size;

        if (index_suffix > 0)
        {
            CUBEFS_TRACE(me_, "import_pages: index_suffix", index_suffix);

            Iterator tmp(me_);
            NodeBase *next_page = tmp.GetNextNode(node);
            if (next_page != NULL && me_.GetCapacity(next_page) >= index_prefix)
            {
                CUBEFS_TRACE(me_, "import_pages: use next page", next_page->id());
                node = next_page;
            }
            else
            {
                idx = 0;
                CUBEFS_TRACE(me_, "import_pages: split page");
                node = me_.SplitBTreeNode(node, me_.GetChildrenCount(node), 0); //TODO ???? why +1 ?
            }

            if (size_prefix == 0 && index_prefix == 0 && total_index_pages == 0)
            {
                *page0  = node;
                idx0   = idx;
                offset0 = 0;
            }

            import_several_pages(node, idx, block, descriptor, index_suffix);

            descriptor.start() += index_suffix * page_size;
            idx = index_suffix; // may be += ???????
        }

        if (size_suffix > 0)
        {
            CUBEFS_TRACE(me_, "import_pages: size_suffix", size_suffix);
            BigInt lp_usage = me_.GetKey(node, 0, idx);

            if (size_suffix <= page_size - lp_usage)
            {
                // do nothing there
            }
            else if (me_.GetCapacity(node) > 0)
            {
                me_.InsertSpace(node, idx, 1);
                me_.create_datapage(node, idx);
            }
            else
            {
                me_.SplitBTreeNode(node, idx, 0);
            }

            if (size_prefix == 0 && index_prefix == 0 && total_index_pages == 0 && index_suffix == 0)
            {
                *page0  = node;
                idx0   = idx;
                offset0 = 0;
            }

            descriptor.length() = size_suffix;
            import_small_block(node, idx, 0, block, descriptor);
        }

        descriptor.length() = length;
    }

    void import_several_pages(
            NodeBase *node,
            BigInt idx,
            const Buffer &block,
            BufferContentDescriptor &descriptor,
            BigInt page_count)
    {
        BigInt length = descriptor.length();
        descriptor.length() = DataPageType::get_max_size();

        BigInt total_indexes[Indexes] = {0};

        for (BigInt c = idx; c < idx + page_count; c++, descriptor.start() += descriptor.length())
        {
            import_data(
                    me_.create_datapage(node, c),
                    c,
                    0,
                    block,
                    descriptor
            );

            BigInt* indexes = descriptor.indexes();
            me_.SetKeys(node, c, indexes);

            for (Int d = 0; d < Indexes; d++)
            {
                total_indexes[d] += indexes[d];
            }
        }

        descriptor.length() = length;

        me_.Reindex(node);

        NodeBase* parent = me_.GetParent(node);

        if (parent != NULL) {
            me_.UpdateBTreeKeys(node, node->parent_idx(), total_indexes);
        }
    }


    void import_small_block(
            NodeBase *node,
            BigInt idx,
            BigInt pos,
            const Buffer &block,
            BufferContentDescriptor &descriptor
    )
    {
        CUBEFS_TRACE(me_, "import_small_block", node->id(), idx, pos, block.GetByteSize());

        DataPageType* data_page = me_.GetDataPage(node, idx);
        if (data_page == NULL)
        {
            data_page = me_.create_datapage(node, idx);
        }

        me_.import_data(data_page, idx, pos, block, descriptor);

        me_.UpdateBTreeKeys(node, idx, descriptor.indexes());
    }


    void import_data(
                DataPageType *page,
                BigInt idx,
                BigInt pos,
                const Buffer &data,
                BufferContentDescriptor &descriptor)
    {
        BigInt usage    = page->data().size();
        BigInt start    = descriptor.start();
        BigInt length   = descriptor.length();

        if (pos < usage)
        {
            page->data().shift(pos, length);
        }

        me_.copy_data(data, page, start, pos, length);

        usage += length;

        page->data().size() = usage;
    }

    void move_data_in_page_create(Iterator &iter, BigInt local_idx, CountData &prefix)
    {
        DataPageType* to = me_.create_datapage(iter.page(), iter.data()->parent_idx() + 1);
        me_.move_data_in_page(iter.data(), to, local_idx, prefix);
    }

    void move_data_in_page_create(DataPageType *from, NodeBase *node, BigInt idx, BigInt local_idx, CountData &prefix)
    {
        DataPageType* to = me_.create_datapage(node, idx);
        move_data_in_page(from, to, local_idx, from->data()->header().get_size(), prefix);
    }

    void move_data_in_page(Iterator &iter, BigInt local_idx, CountData &prefix)
    {
        DataPageType *to = me_.GetDataPage(iter.page(), iter.data()->parent_idx() + 1);
        me_.move_data_in_page(iter.data(), to, local_idx, prefix);
    }

    void move_data_in_page(DataPageType *from, DataPageType *to, BigInt local_idx, CountData &prefix)
    {
        BigInt keys[Indexes];
        me_.move_data(from, to, local_idx, prefix, keys);

//        NodeBase *from_node = me_.GetParent(from);
//        me_.UpdateBTreeKeys(from_node, from->parent_idx(), keys);
//
//        for (Int c = 0; c < Indexes; c++) keys[c] = -keys[c];
//
//        NodeBase *to_node = me_.GetParent(to);
//        me_.UpdateBTreeKeys(to_node, to->parent_idx(), keys);
    }

CUBEFS_MODEL_PART_END



}
}

#undef CUBEFS_SOURCE

#endif
